package Hot100;

import Tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class 路径总和3 {

    Map<Long, Integer> preSumCount = new HashMap<>();
    int targetSum;

    public int pathSum(TreeNode root, int targetSum) {
        preSumCount.put(0L, 1);
        this.targetSum = targetSum;
        return recurPathSum(root, 0);
    }

    private int recurPathSum(TreeNode root, long curSum) {
        if (root == null) return 0;
        curSum += root.val;
        int midCount = preSumCount.getOrDefault(curSum - targetSum, 0);
        preSumCount.put(curSum, preSumCount.getOrDefault(curSum, 0) + 1);
        int leftCount = recurPathSum(root.left, curSum);
        int rightCount = recurPathSum(root.right, curSum);
        preSumCount.put(curSum, preSumCount.get(curSum) - 1);
        return midCount + leftCount + rightCount;
    }
}
